package main

type ListNode struct {
	Val  int
	Next *ListNode
}

func doReverse(start *ListNode, end *ListNode) (*ListNode, *ListNode) {
	prev := end.Next
	n := start
	for prev != end {
		next := n.Next
		n.Next = prev
		prev = n
		n = next
	}
	return end, start
}

func reverseKGroup(head *ListNode, k int) *ListNode {
	hair := &ListNode{Next: head}
	prev := hair
	for head != nil {
		tail := prev
		for i := 0; i < k; i++ {
			tail = tail.Next
			if tail == nil {
				return hair.Next
			}
		}
		next := tail.Next
		head, tail = doReverse(head, tail)
		prev.Next = head
		prev = tail
		head = next
	}
	return hair.Next
}


func main() {
	n0 := &ListNode{Val: 1}
	n1 := &ListNode{Val: 2}
	n2 := &ListNode{Val: 3}
	n3 := &ListNode{Val: 4}
	n4 := &ListNode{Val: 5}
	n0.Next = n1
	n1.Next = n2
	n2.Next = n3
	n3.Next = n4
	res := reverseKGroup(n0, 2)
	println(res)
}
